package org.example.leetcode.interview.stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class LC0020 {
    /**
     * 括号完全匹配的意味着进栈出栈一通操作后最后栈的大小是0, isEmpty返回true
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        char[] chars = s.toCharArray();
        for (char ch : chars) {
            if (!map.containsKey(ch)) {
                stack.push(ch);
            } else {
                // 栈空了, 进来个(或[或{自然非法
                // 或者栈顶的元素不是map里对应括号的另一半
                if (stack.isEmpty() || stack.peek() != map.get(ch)) {
                    return false;
                }
                stack.pop();
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        LC0020 solu = new LC0020();
//        solu.isValid("()");
//        solu.isValid("()[]{}");
//        solu.isValid("(]");
        System.out.println(solu.isValid("]"));;
    }
}
